#include<iostream>
#include<cstring>
#define INF 1e7

using namespace std;

int dis_twoPoint[2001][2001];   //记录各个点之间的距离
int disFromSource[1001]; //从源点到各个目的地的最短距离

void dijstra(int n){
    int isFoundDis[1001]={0};     //标记是否已经确定最短距离
    int MAX,flag;
    for(int i=1;i<=n;i++){
        disFromSource[i]=dis_twoPoint[1][i];     //源点到各个点的第一轮距离/初始化
    }
    for(int i=1;i<=n;i++){  //开始循环寻找最短距离
        MAX=INF;
        flag=0;
        for(int j=2;j<=n;j++){
            if(disFromSource[j]<MAX&&!isFoundDis[j]){  //找到每一轮最短且没有被标记已经确定距离的节点
                MAX=disFromSource[j];
                flag=j;     //用flag标记
            }
        }
        isFoundDis[flag]=1;   //已经确定最短距离
        for(int j=2;j<=n;j++){      //对其他的重新确定目前距离
            if(disFromSource[j]>MAX+dis_twoPoint[flag][j]&&!isFoundDis[j]){
                disFromSource[j]=MAX+dis_twoPoint[flag][j];
            }
        }
    }
}

int main(void){
    int t,i,n,k,m,dis;
    while(cin>>t>>n){
        for(int i=1;i<=2000;i++){   //temp初始化
            dis_twoPoint[i][i]=0;
        }
        for(int i=1;i<=2000;i++){       //temp初始化
            for(int j=1;j<=2000;j++){
                dis_twoPoint[i][j]=INF;
            }
        }
        for(int i=1;i<=t;i++){
            cin>>k>>m>>dis;
            if(dis<dis_twoPoint[k][m]||dis<dis_twoPoint[m][k]){     //录入temp，双向
                dis_twoPoint[k][m]=dis;
                dis_twoPoint[m][k]=dis;
            }
        }
        dijstra(n);
        cout<<disFromSource[n]<<endl;
    }
    return 0;
}